class NPSPACE

Definition

$\mathbf{NPSPACE}$ represents decision problems decidable by a NDTM, i.e.

(NSPACE)

Proposition

$\mathbf{NPSPACE} =$ PSPACE

Notes

• PSPACE and NSPACE can be thought of as the space analogs of time complexity classes P and NP respectively

See also

• Savitch's theorem: $\mathbf{NSPACE}(s(n)) \subseteq \mathbf{DSPACE}(s(n)^2)$

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 81.
2. https://en.wikipedia.org/wiki/NSPACE
3. https://home.csulb.edu/~tebert/teaching/lectures/419-519/pspace/pspace.pdf
4. https://webdocs.cs.ualberta.ca/~zacharyf/courses/complexity_2019/notes/complexity-w19-lec03.pdf
5. https://mathoverflow.net/questions/39690/how-is-p-related-to-other-complexity-classes
6. https://www.cs.ubc.ca/~condon/cpsc506/lectures/lec4.pdf